Acabamos de estabelecer que as Listas Encadeadas utilizam ponteiros dinâmicos para atualizações eficientes em $O(1)$ quando o número de elementos, $n$, é volátil. Agora, devemos compreender a estrutura com a qual são mais frequentemente comparadas: o Array.

  • Um array é definido pelo uso de memória contígua. Todos os elementos são armazenados adjacentes uns aos outros em um único bloco de memória.
  • Essa estrutura permite acesso aleatório, ou seja, qualquer elemento pode ser acessado diretamente sem percorrer os elementos anteriores.
  • O endereço de memória de um elemento no índice $i$ é calculado usando a fórmula: $EndereçoBase + i \times TamanhoElemento$.
  • Esse cálculo garante que ler ou acessar qualquer item seja uma operação incrivelmente eficiente, sempre concluindo em $O(1)$ complexidade de tempo.
  • No entanto, inserção ou exclusão no meio exige deslocar $O(n)$ elementos para manter a continuidade, tornando essas operações lentas.

Propriedade Fundamental: Acesso Aleatório

Um array é uma coleção sequencial onde a ordem física na memória corresponde diretamente à ordem lógica dos elementos. O uso de índices permite calcular instantaneamente a localização exata na memória de qualquer item, garantindo tempo de acesso de $O(1)$.